一、學習目標

• 了解 set、unordered_set 的差異與使用情境。
• 學會如何利用這兩種容器高效處理「去重」、「查找」、「區間維護」。

二、STL Set 與 Unordered_Set 教學

1. set（有序集合）

特點：

• 元素自動排序（預設升序）。
• 元素唯一。
• 底層實作為紅黑樹。

常見操作：

set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
// s = {1, 2, 3}
s.erase(2);       // 移除 2
cout << s.count(3); // 查找 3，存在回傳 1

時間複雜度：
插入、刪除、查找 → O(logn)

2. unordered_set（無序集合）

特點：

• 元素不排序。
• 元素唯一。
• 底層實作為哈希表。

常見操作：

unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(2);
// us = {1, 2, 3}，但順序不保證
cout << us.count(3); // 查找 3，存在回傳 1

時間複雜度：
插入、刪除、查找 → 平均 O(1)

兩者差異比較

CSES 實戰題目

題目 1：Distinct Numbers

原題:
https://cses.fi/problemset/task/1621
題意:
給定 n 個整數，輸出有多少個不重複的整數。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // 加速 cin/cout
    cin.tie(0);

    int n;
    cin >> n;

    unordered_set<int> s; 
    s.reserve(n * 2);   // 提前配置空間，避免 rehash
    s.max_load_factor(0.7); // 降低碰撞率，加速插入

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    cout << s.size() << "\n";
    return 0;
}

• s.reserve() → 預先分配記憶體，避免多次 rehash
• s.max_load_factor() → 降低哈希碰撞，插入更快

題目 2：Traffic Lights

原題:
https://cses.fi/problemset/task/1163
題意:
有一條長度為 x 的道路，初始時沒有紅綠燈。
接下來會依序安裝 n 個紅綠燈，每次安裝後，輸出目前最大連續道路區間長度。

實作步驟:
用 set 儲存紅綠燈位置，保持有序。
用 set<pair<int,int>> 儲存「道路區間」，每個區間用 (長度, 左端點) 表示。
每次插入紅綠燈：

• 找到「右端點」：right = lights.lower_bound(pos)
• 找到「左端點」：left = prev(right)
• 從 segs 中刪除舊區間 (right - left, left)
• 插入兩個新區間：
  • (pos - left, left)
  • (right - pos, pos)
• 更新紅綠燈集合。
  最大區間長度 = segs.rbegin()->first

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int x, n;
    cin >> x >> n;

    set<int> lights = {0, x};  // 儲存紅綠燈位置（有序）
    set<pair<int,int>> segs = {{x, 0}}; // 儲存區間，依照長度排序 (長度, 左端點)

    for (int i = 0; i < n; i++) {
        int pos;
        cin >> pos;

        // 找右端與左端
        auto right = lights.lower_bound(pos);
        auto left = prev(right);

        // 從 segs 中移除舊區間
        segs.erase({*right - *left, *left});

        // 插入新區間
        segs.insert({pos - *left, *left});
        segs.insert({*right - pos, pos});

        // 更新紅綠燈位置
        lights.insert(pos);

        // 取得目前最大區間長度
        cout << segs.rbegin()->first << " ";
    }
    cout << "\n";
    return 0;
}

Leetcode 實戰題目

題目 1：Happy number

原題:
https://leetcode.com/problems/happy-number/description/

題意:
對一個正整數，不斷將它的每個位數平方再相加，最終若能變成 1，則稱為「快樂數」。
若陷入循環，永遠無法得到 1，則不是快樂數。

思路:
要檢測循環，用 unordered_set 儲存曾經出現過的數字：
若新數字在 set 中 → 表示進入循環 → 回傳 false。
否則繼續計算，直到得到 1。

class Solution {
public:
    // 計算下一個數字（每位數平方和）
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;
            sum += d * d;
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        unordered_set<int> seen;  // 紀錄出現過的數字
        while (n != 1 && !seen.count(n)) {
            seen.insert(n);
            n = getNext(n);
        }
        return n == 1;
    }
};

註:此題有更優解，只是需要做unorder_set的範例！

題目 2：Happy number

原題:
https://leetcode.com/problems/intersection-of-two-arrays/description/
題意:
給定兩個整數陣列，找出它們的交集，結果中的元素必須唯一。

解題思路:
用 unordered_set 加速查找。
步驟：

• 把第一個陣列元素放入 set1。
• 遍歷第二個陣列，若元素存在於 set1，加入 set2。
• 最後把 set2 轉換為向量返回。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 使用 unordered_set 儲存第一個陣列
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> result;

        // 遍歷第二個陣列，檢查是否存在於 set1
        for (int num : nums2) {
            if (set1.count(num)) {
                result.insert(num);
            }
        }

        // 將結果轉為 vector
        return vector<int>(result.begin(), result.end());
    }
};